package com.example.algorithm.dynamicprogramming;

/**
 * 集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
 *  第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
 *
 *  工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
 *  有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
 *
 *  示例 1：
 * 输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
 * 输出：2
 * 解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
 * 总的来说，有两种计划。
 *
 *  示例 2：
 * 输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
 * 输出：7
 * 解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
 * 有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
 */
public class Leetcode879_ProfitableSchemes {
    public static void main(String[] args) {
        int n = 5;
        int minProfit = 3;
        int[] group = {2, 2};
        int[] profit = {2, 3};

        n = 10;
        minProfit = 5;
        group = new int[] {2, 3, 5};
        profit = new int[] {6, 7, 8};

        // 95
        //53
        //[82,7,18,34,1,3,83,56,50,34,39,38,76,92,71,2,6,74,1,82,22,73,88,98,6,71,6,26,100,75,57,88,43,16,22,89,7,9,78,97,22,87,34,81,74,56,49,94,87,71,59,6,20,66,64,37,2,42,30,87,73,16,39,87,28,9,95,78,43,59,87,78,2,93,7,22,21,59,68,67,65,63,78,20,82,35,86]
        //[45,57,38,64,52,92,31,57,31,52,3,12,93,8,11,60,55,92,42,27,40,10,77,53,8,34,87,39,8,35,28,70,32,97,88,54,82,54,54,10,78,23,82,52,10,49,8,36,9,52,81,26,5,2,30,39,89,62,39,100,67,33,86,22,49,15,94,59,47,41,45,17,99,87,77,48,22,77,82,85,97,66,3,38,49,60,66]
        n = 95;
        minProfit = 53;
        group = new int[] {82,7,18,34,1,3,83,56,50,34,39,38,76,92,71,2,6,74,1,82,22,73,88,98,6,71,6,26,100,75,57,88,43,16,22,89,7,9,78,97,22,87,34,81,74,56,49,94,87,71,59,6,20,66,64,37,2,42,30,87,73,16,39,87,28,9,95,78,43,59,87,78,2,93,7,22,21,59,68,67,65,63,78,20,82,35,86};
        profit = new int[] {45,57,38,64,52,92,31,57,31,52,3,12,93,8,11,60,55,92,42,27,40,10,77,53,8,34,87,39,8,35,28,70,32,97,88,54,82,54,54,10,78,23,82,52,10,49,8,36,9,52,81,26,5,2,30,39,89,62,39,100,67,33,86,22,49,15,94,59,47,41,45,17,99,87,77,48,22,77,82,85,97,66,3,38,49,60,66};
        System.out.println(new Solution().profitableSchemes(n, minProfit, group, profit));

    }

    static class Solution {
        /**
         * 动态规划
         *
         * 前 i个工作选择了j个员工并且满足工作利润  至少为 k  的情况下的盈利计划的总数目 dp[i][j][k]
         *   如果不能够完成第i个工作(if j < group[i])
         *     dp[i][j][k] = dp[i - 1][j][k]
         *  否则(能完成第 i 个工作)
         *     dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - group[i]][Math.max(0, k - profit)]
         *     即: 完成前 i-1 个任务选择了j个员工的最大利润至少为k (dp[i - 1][j][k])  +
         *        完成前 i-1 个任务选择了 j - group[i] 个员工 大利润至少为k - profit (dp[i - 1][j - group[i]][max(0, k - profit)])
         *        ()
         *
         *
         * @param n
         * @param minProfit
         * @param group
         * @param profits
         * @return
         */
        private int profitableSchemes2(int n, int minProfit, int[] group, int[] profits) {
            int len = group.length, MOD = (int)1e9 + 7;
            int[][][] dp = new int[len + 1][n + 1][minProfit + 1]; // dp[i][j][k] 表示在前 i 个工作中选择了 j 个员工，并且满足工作利润至少为 k 的情况下的盈利计划的总数目

            dp[0][0][0] = 1;
            for (int i = 1; i <= len; i++) {
                int needPersonSize = group[i - 1], profit = profits[i - 1];
                for (int j = 0; j <= n; j++) {
                    for (int k = 0; k <= minProfit; k++) {
                        if (j < needPersonSize) { // 无法开展当前工作 i 的情况
                            dp[i][j][k] = dp[i - 1][j][k];
                        } else { // 能够开展当前工作 i 的情况
                            int y = j - needPersonSize;
                            int z = Math.max(0, k - profit);
                            dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][y][z]) % MOD;
                        }
                    }
                }
            }

            int res = 0;
            for (int j = 0; j <= n; j++) {
                res = (res + dp[len][j][minProfit]) % MOD;
            }
            return res;
        }

        /**
         * 解法一：动态规划(数据d多了有问题)
         * 1.原问题与子问题
         *   求解完成以 group[i] 为结尾的工作能达到最少利润的盈利计划数
         *
         * 2.设计状态
         *   dp[i]表示完成以group[i]为结尾的工作能达到最少利润的盈利计划数
         *
         * 3.状态转移方程
         *   初始状态：dp[i] = (group[i] <= n && profit[i] >= minProfit) ? 1 : 0;
         *   dp[i]求法(以 i 为结尾的可以看成原来以 j (0 <= j <i) 结尾的再在后面加上一个i)
         *   遍历 0 ~ i -1
         *      if ((group[i] + group[j] <= n) && (profit[i] + profit[j] >= minProfit))
         *         dp[i] += dp[j](if dp[j] == 0 dp[j] = 1)
         *
         * 4.边界值
         * @param n
         * @param minProfit
         * @param group
         * @param profit
         * @return
         */
        private int profitableSchemes1(int n, int minProfit, int[] group, int[] profit) {
            int[] dp = new int[group.length]; // dp[i]表示完成以group[i]为结尾的工作能达到最少利润的盈利计划数

            int res = (minProfit == 0 ? 1 : 0); // 最小利润为0,可以一个任务都不完成(初始结果为1)
            int mod = (int)(1e9 + 7);

            for (int i = 0; i < dp.length; i++) {
                int tmpTotalPerson = group[i];
                int tmpTotalProfit = profit[i];
                dp[i] = (group[i] <= n && profit[i] >= minProfit) ? 1 : 0;

                for (int j = 0; j < i; j++) {
                    if ((tmpTotalPerson + group[j] <= n) && (tmpTotalProfit + profit[j] >= minProfit)) {
                        int tmp = (dp[j] == 0 ? 1 : dp[j]);// 有可能某个任务为结尾不能达到最小利润(此时 dp[j] = 0)，但是加上i任务可以达到最低利润
                        dp[i] = (dp[i] +  tmp) % mod;
                    }
                }
                res = (res + dp[i]) % mod;
            }

            return res;
        }

        public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
            return profitableSchemes1(n, minProfit, group, profit);
        }
    }
}
